Barrel shifters are known electronic circuits. A barrel shifter comprises a buffer and a means for providing a movable window at an output thereof. In a recirculating barrel shifter, the buffer is circular and when the window keeps moving around the circular buffer--its start location incremented between cycles.
Barrel shifters are used for data decompression when variable bit compression schemes are used. Barrel shifters are also used in arithmetic function implementations, circular buffer circuits, parallel processing, control systems, and so forth. The use of barrel shifters in different applications has been included in patent applications since at least as early as Feb. 22, 1982. The use of barrel shifter circuits for encoding and decoding as described in some of the patents below, applies to compression and decompression algorithms where a plurality of bits is compressed into a smaller number of bits and look up tables are necessary to determine a shift amount for each processing cycle.
Examples of U.S. patents describing circuits or systems using barrel shifters include U.S. Pat. No. 5,650,781 entitled Apparatus for decoding variable length codes; U.S. Pat. No. 5,646,874 entitled Multiplication/multiplication-accumulation method and computing device; U.S. Pat. No. 5,646,873 entitled Barrel shifter device and variable-length decoder; U.S. Pat. No. 5,642,115 entitled Variable length coding system; U.S. Pat. No. 5,634,065 entitled Three input arithmetic logic unit with controllable shifter and mask generator; U.S. Pat. No. 5,621,405 entitled Variable-length decoding apparatus using relative address; U.S. Pat. No. 5,619,200 entitled Code table reduction apparatus for variable length decoder; U.S. Pat. No. 5,619,198 entitled Number format conversion apparatus for signal processing; U.S. Pat. No. 5,604,499 entitled Variable-length decoding apparatus; U.S. Pat. No. 5,600,847 entitled Three input arithmetic logic unit with mask generator; U.S. Pat. No. 5,594,927 entitled Apparatus and method for aligning data transferred via DMA using a barrel shifter and a buffer comprising of byte-wide, individually addressabe FIFO circuits; U.S. Pat. No. 5,590,350 entitled Three input arithmetic logic unit with mask generator; U.S. Pat. No. 5,561,690 entitled High speed variable length code decoding apparatus; U.S. Pat. No. 5,557,734 entitled Cache burst architecture for parallel processing, such as for image processing; U.S. Pat. No. 5,557,563 entitled Data processing method and apparatus including iterative multiplier; U.S. Pat. No. 5,555,202 entitled Low-power, high-performance barrel shifter; U.S. Pat. No. 5,553,010 entitled Data shifting circuit capable of an original data width rotation and a double data width rotation; U.S. Pat. No. 5,542,074 entitled Parallel processor system with highly flexible local control capability, including selective inversion of instruction signal and control of bit shift amount; U.S. Pat. No. 5,532,949 entitled Barrel shifter; U.S. Pat. No. 5,529,071 entitled Increasing dynamic range with a barrel shifter; U.S. Pat. No. 5,526,296 entitled Bit field operating system and method with two barrel shifters for high speed operations; U.S. Pat. No. 5,517,436 entitled Digital signal processor for audio applications; U.S. Pat. No. 5,509,129 entitled Long instruction word controlling plural independent processor operations; U.S. Pat. No. 5,499,382 entitled Circuit and method of bit-packing and bit-unpacking using a barrel shifter; U.S. Pat. No. 5,481,583 entitled Higher order preinterpolator for backprojection; U.S. Pat. No. 5,479,527 entitled Variable length coding system; U.S. Pat. No. 5,477,477 entitled Data shifting circuit by utilizing MOS barrel shifter; U.S. Pat. No. 5,471,628 entitled Multi-function permutation switch for rotating and manipulating an order of bits of an input data byte in either cyclic or non-cyclic mode; U.S. Pat. No. 5,465,223 entitled Barrel shifter; U.S. Pat. No. 5,465,222 entitled Barrel shifter or multiply/divide IC structure; U.S. Pat. No. 5,463,638 entitled Control device for interface control between a test machine and multi-channel electronic circuitry, in particular according to boundary test standard; U.S. Pat. No. 5,457,723 entitled Barrel shifter having CMOS structure integrated on MOS integrated circuits; U.S. Pat. No. 5,450,607 entitled Unified floating point and integer datapath for a RISC processor; U.S. Pat. No. 5,432,512 entitled Apparatus for decoding variable length codes; U.S. Pat. No. 5,420,584 entitled Data converter with barrel shifter; U.S. Pat. No. 5,416,731 entitled High-speed barrel shifter; U.S. Pat. No. 5,404,138 entitled Apparatus for decoding variable length codes; U.S. Pat. No. 5,343,195 entitled Variable length codeword decoding apparatus; U.S. Pat. No. 5,381,454 entitled Circuit and method of resetting a data compressor/decompressor; U.S. Pat. No. 5,309,156 entitled Variable-length code decoding device; U.S. Pat. No. 5,295,250 entitled Microprocessor having barrel shifter and direct path for directly rewriting output data of barrel shifter to its input; U.S. Pat. No. 5,282,152 entitled Integer-based 18-bit RGB to 5-bit gray scale conversion device and method therefor; U.S. Pat. No. 5,262,971 entitled Bidirectional shifter; U.S. Pat. No. 5,247,627 entitled Digital signal processor with conditional branch decision unit and storage of conditional branch decision results; U.S. Pat. No. 5,245,637 entitled Phase and frequency adjustable digital phase lock logic system; U.S. Pat. No. 5,245,338 entitled High-speed variable-length decoder; U.S. Pat. No. 5,241,490 entitled Fully decoded multistage leading zero detector and normalization apparatus; U.S. Pat. No. 5,237,667 entitled Digital signal processor system having host processor for writing instructions into internal processor memory; U.S. Pat. No. 5,223,832 entitled Serial data transmission circuit; U.S. Pat. No. 5,222,241 entitled Digital signal processor having duplex working registers for switching to standby state during interrupt processing; U.S. Pat. No. 5,220,670 entitled Microprocessor having ability to carry out logical operation on internal bus; U.S. Pat. No. 5,206,940 entitled Address control and generating system for digital signal-processor; U.S. Pat. No. 5,187,678 entitled Priority encoder and floating-point normalization system for IEEE 754 standard; U.S. Pat. No. 5,173,695 entitled High-speed flexible variable-length-code decoder; U.S. Pat. No. 5,161,117 entitled Floating point conversion device and method; U.S. Pat. No. 5,155,698 entitled Barrel shifter circuit having rotation function; U.S. Pat. No. 5,146,220 entitled Data conversion method and apparatus for converting undefined length data to fixed length data; U.S. Pat. No. 5,144,573 entitled Barrel shifter with parity bit generator; U.S. Pat. No. 5,130,941 entitled Dynamic barrel shifter; U.S. Pat. No. 5,130,940 entitled Barrel shifter for data shifting; U.S. Pat. No. 5,081,700 entitled Apparatus for high speed image rotation; U.S. Pat. No. 5,060,242 entitled Non-destructive lossless image coder; U.S. Pat. No. 5,045,993 entitled Digital signal processor; U.S. Pat. No. 5,040,138 entitled Circuit for simultaneous arithmetic calculation and normalization estimation; U.S. Pat. No. 5,031,135 entitled Device for multi-precision and block arithmetic support in digital processors; U.S. Pat. No. 5,029,121 entitled Digital filter processing device; U.S. Pat. No. 5,027,306 entitled Decimation filter as for a sigma-delta analog-to-digital converter; U.S. Pat. No. 4,983,958 entitled Vector selectable coordinate-addressable DRAM array; U.S. Pat. No. 4,980,853 entitled Bit blitter with narrow shift register; U.S. Pat. No. 4,979,175 entitled State metric memory arrangement for a viterbi decoder; U.S. Pat. No. 4,979,139 entitled Arithmetic unit for exponential function; U.S. Pat. No. 4,973,956 entitled Crossbar switch with distributed memory; U.S. Pat. No. 4,962,511 entitled Barrel shifter; U.S. Pat. No. 4,962,500 entitled Data processor including testing structure for a barrel shifter; U.S. Pat. No. 4,958,311 entitled Composite finite impulse response digital filter; U.S. Pat. No. 4,943,941 entitled Floating point processor employing counter controlled shifting; U.S. Pat. No. 4,939,684 entitled Simplified processor for digital filter applications; U.S. Pat. No. 4,914,622 entitled Array-organized bit map with a barrel shifter; U.S. Pat. No. 4,905,178 entitled Fast shifter method and structure; U.S. Pat. No. 4,901,263 entitled Versatile data shifter with sticky bit generation capability; U.S. Pat. No. 4,899,302 entitled Arithmetic unit for inverse trigonometric function; U.S. Pat. No. 4,887,232 entitled Apparatus and method for performing a shift operation in a multiplier array circuit; U.S. Pat. No. 4,862,407 entitled Digital signal processing apparatus; U.S. Pat. No. 4,839,840 entitled Highly responsive barrel shifter; U.S. Pat. No. 4,839,839 entitled Barrel shifter including rotate operation; U.S. Pat. No. 4,831,571 entitled Barrel shifter for rotating data with or without carry; U.S. Pat. No. 4,829,460 entitled Barrel shifter; U.S. Pat. No. 4,827,441 entitled Barrel shifter; U.S. Pat. No. 4,817,047 entitled Processing circuit capable of raising throughput of accumulation; U.S. Pat. No. 4,811,268 entitled Processing circuit capable of raising throughput of accumulation; U.S. Pat. No. 4,807,043 entitled Two-dimensional facsimile encoding apparatus with coding and reference line windowing means and color change detectors; U.S. Pat. No. 4,782,457 entitled Barrel shifter using bit reversers and having automatic normalization; U.S. Pat. No. 4,779,223 entitled Display apparatus having an image memory controller utilizing a barrel shifter and a mask controller preparing data to be written into an image memory; U.S. Pat. No. 4,779,220 entitled Floating-point data rounding and normalizing circuit; U.S. Pat. No. 4,760,544 entitled Arithmetic logic and shift device; U.S. Pat. No. 4,755,810 entitled Frame buffer memory; U.S. Pat. No. 4,747,154 entitled Image data expanding and/or contracting method and apparatus; U.S. Pat. No. 4,740,993 entitled Digital companding circuit; U.S. Pat. No. 4,665,538 entitled Bidirectional barrel shift circuit; U.S. Pat. No. 4,653,019 entitled High speed barrel shifter; U.S. Pat. No. 4,512,018 entitled Shifter circuit; and U.S. Pat. No. 4,488,252 entitled Floating point addition architecture.
In the past, three common approaches to variable bit encoding were used. The earlier of these methods, serial input to serial output, is useful at low communication rates as were common until a few years ago. A hybrid, serial input to parallel output, suffers disadvantages outlined below. The latter, parallel input to parallel output, is useful at higher bit rates and is advantageous over the earlier approach.
Devices incorporating the earlier, and more common, approach provide a serial stream of bits at an output thereof. Data is provided to the encoder device. The data is encoded according to an encoding algorithm and the encoded data is provided to a shift register. The shift register acts as a 1 bit wide FIFO (first in first out memory) and all the bits are shifted toward the output. Each clock cycle, a bit is extracted from the shift register and all the bits are again shifted. New bits provided to the shift register are shifted down until they are adjacent to any previously provided bits that are awaiting extraction.
It is evident that such a device is very suitable for low speed operation. At speeds of kilobits per second, or even several megabits per second, circuit speeds for current semiconductor technology, integrated circuit costs, and noise considerations are easily balanced to provide working circuitry.
In known serial input to parallel output shift registers, a serial bit stream is clocked through a series of serial registers and latched into parallel outputs. The number of parallel bits on the output is dependent on the number of bits shifted serially through the registers before a parallel latch is enabled.
Such a device has certain known shortcomings, for example, in a bit stuffing multiplexer circuit. A bit stuffing multiplexer inputs a signal at one frequency and stuffs (adds) bits into that signal, thus outputting a signal at a higher frequency. Such are useful in multiplexing schemes for interleaving signals of different rates. See, for example, American National Standards for Telecommunications, Digital Hierarchy-Optical Interface Rates and Formats Specification, ANSI T1.105-1988. The multiplexer circuit consists of a buffer, buffer write controller and a buffer read controller. The serial input to parallel output shift register will be located in the write controller and will generate the bit stuffing pattern by outputting gaps in the input signal where stuff data will be located. The read controller will generate the output signal framing pattern by placing additional gaps in the input signal.
The shortcomings of the above mentioned device in the bit stuffing multiplexer example are that (1) the location of the start of the bit stuffing pattern determined by the write controller cannot easily be fixed relative to the framing pattern, and (2) a control signal(s) from the write controller to the read controller must be passed through the buffer. The bit stuffing pattern is generated using a clock on the input side of the buffer, a clock that is asynchronous to the output clock. Therefore, when the circuit is initialized, the bit stuffing pattern will start at random locations relative to the framing pattern if control signals were passed through an additional buffer, but padding control signals through a buffer creates other shortcomings. If the circuit writing the control signals into the buffer fails when a control signal is in the buffer then read control circuit data corruption or framing pattern corruption may result.
With the advent of ATM and higher Ethernet speeds, communications systems now operate at speeds up to several Gigabits per second. At these speeds integrated circuit speed and noise pose significant constraints on shift register implementations. Solutions, when possible, require very costly materials or processes to accomplish a shift register implementation of a high speed communications encoding device.
In U.S. Pat. No. 5,272,703 entitled "N-Bit Parallel Input to Variable-Bit Parallel Output Shift Register" in the name of Peters, a parallel input to parallel output shift register is disclosed in an attempt to overcome the limitations of earlier serial to parallel encoding devices. The circuit disclosed recirculates data bits which are not output during the cycle to the shift register for output during a subsequent cycle. This allows for bit stuffing where the output bit rate is lower than the rate at which bits accumulate within the shift register.
A known disadvantage of the circuit described by Peters is that the shift register implementation is complex and requires high speed integrated circuits for the recirculation circuitry where bits must be recirculated within a single clock cycle; during a single clock cycle, the data is provided to a multiplexer, stabilises at the multiplexer input and at the multiplexer output, stabilises at the shift register input, is clocked into the shift register, and stabilises at the shift register output. When using programmable logic such as that available from Xilinx.RTM. a nominal delay of 10 ns results. For eight bit parallel data, a maximum speed of about 800 Megabits per second results.
It would be advantageous to provide a simpler circuit that is capable of operating at higher speeds implemented using similar integrated circuit technologies.